Developer CD Series 1996 February: Tool Chest

home *** CD-ROM | disk | FTP | other *** search

/ Developer CD Series 1996 February: Tool Chest / Apple Developer CD Series Tool Chest February 1996 (Apple Computer)(1996).iso / Tool Chest / Development Tools & Languages / Macintosh Common Lisp Related / Lisp FAQ 14Sept94 / 1.Intro&References next >

Wrap

Internet Message Format | 1994-09-15 | 72.7 KB | [TEXT/ttxt]

Subject: FAQ: Lisp Frequently Asked Questions 1/7 [Monthly posting] Newsgroups: comp.lang.lisp,news.answers,comp.answers Summary: Introductory Matter and Bibliography of Introductions and References Distribution: world Followup-To: poster Reply-To: ai+lisp-faq@cs.cmu.edu Approved: news-answers-request@MIT.Edu Archive-name: lisp-faq/part1 Last-Modified: Wed Sep 14 16:36:28 1994 by Mark Kantrowitz Version: 1.50 Maintainer: Mark Kantrowitz and Barry Margolin <ai+lisp-faq@cs.cmu.edu> URL: http://www.cs.cmu.edu:8001/Web/Groups/AI/html/faqs/lang/lisp/top.html Size: 74423 bytes, 1528 lines ;;; **************************************************************** ;;; Answers to Frequently Asked Questions about Lisp *************** ;;; **************************************************************** ;;; Written by Mark Kantrowitz and Barry Margolin ;;; lisp_1.faq This post contains Part 1 of the Lisp FAQ. If you think of questions that are appropriate for this FAQ, or would like to improve an answer, please send email to us at ai+lisp-faq@cs.cmu.edu. Note that the lisp-faq mailing list is for discussion of the content of the FAQ posting only. It is not the place to ask questions about Lisp; use either the common-lisp@ai.sri.com mailing list or the comp.lang.lisp newsgroup for that. If a question appears frequently in one of those forums, it will get added to the FAQ list. *** Copyright: Copyright (c) 1992-94 by Mark Kantrowitz and Barry Margolin. All rights reserved. This FAQ may be freely redistributed in its entirety without modification provided that this copyright notice is not removed. It may not be sold for profit or incorporated in commercial documents (e.g., published for sale on CD-ROM, floppy disks, books, magazines, or other print form) without the prior written permission of the copyright holder. Permission is expressly granted for this document to be made available for file transfer from installations offering unrestricted anonymous file transfer on the Internet. This article is provided AS IS without any express or implied warranty. *** Topics Covered: There are currently seven parts to the Lisp FAQ: 1. Introductory Matter and Bibliography of Introductions and References 2. General Questions 3. Common Programming Pitfalls 4. Lisp Implementations and Mailing Lists 5. Object-oriented Programming in Lisp 6. FTP Archives and Resources 7. Lisp Window Systems and GUIs All parts are posted to comp.lang.lisp. Part 5 is cross-posted to the comp.lang.clos newsgroup. Topics Covered (Part 1): [1-0] What is the purpose of this newsgroup? [1-1] What is the difference between Scheme and Common Lisp? [1-2] Lisp books, introductions, documentation, periodicals, journals, and conference proceedings. [1-3] How can I improve my Lisp programming style and coding efficiency? [1-4] Where can I learn about implementing Lisp interpreters and compilers? [1-5] What is the "minimal" set of primitives needed for a Lisp interpreter? [1-6] What does CLOS, PCL, X3J13, CAR, CDR, ... mean? [1-7] Lisp Job Postings Topics Covered (Part 2): [2-1] Is there a GNU-Emacs interface to Lisp? [2-2] When should I use a hash table instead of an association list? [2-3] What is the equivalent of EXPLODE and IMPLODE in Common Lisp? [2-4] Is Lisp inherently slower than more conventional languages such as C? [2-5] Why does Common Lisp have "#'"? [2-6] How do I call non-Lisp functions from Lisp? [2-7] Can I call Lisp functions from other languages? [2-8] I want to call a function in a package that might not exist at compile time. How do I do this? [2-9] What is CDR-coding? [2-10] What is garbage collection? [2-11] How do I save an executable image of my loaded Lisp system? How do I run a Unix command in my Lisp? [2-12] I'm porting some code from a Symbolics Lisp machine to some other platform, and there are strange characters in the code. What do they mean? [2-13] History: Where did Lisp come from? [2-14] How do I find the argument list of a function? How do I get the function name from a function object? [2-15] How can I have two Lisp processes communicate via unix sockets? [2-16] How can I create a stream that acts like UNIX's /dev/null (i.e., gobbles any output and immediately signals EOF on input operations)? [2-17] Read-time conditionalization of code (#+ #- and *features*) [2-18] What reader macro characters are used in major Lisp systems? [2-19] How do I determine if a file is a directory or not? How do I get the current directory name from within a Lisp program? Is there any way to create a directory? [2-20] What is a "Lisp Machine" (LISPM)? Common Pitfalls (Part 3): [3-0] Why does (READ-FROM-STRING "foobar" :START 3) return FOOBAR instead of BAR? [3-1] Why can't it deduce from (READ-FROM-STRING "foobar" :START 3) that the intent is to specify the START keyword parameter rather than the EOF-ERROR-P and EOF-VALUE optional parameters? [3-2] Why can't I apply #'AND and #'OR? [3-3] I used a destructive function (e.g. DELETE, SORT), but it didn't seem to work. Why? [3-4] After I NREVERSE a list, it's only one element long. After I SORT a list, it's missing things. What happened? [3-5] Why does (READ-LINE) return "" immediately instead of waiting for me to type a line? [3-6] I typed a form to the read-eval-print loop, but nothing happened. Why? [3-7] DEFMACRO doesn't seem to work. When I compile my file, LISP warns me that my macros are undefined functions, or complains "Attempt to call <function> which is defined as a macro. [3-8] Name conflict errors are driving me crazy! (EXPORT, packages) [3-9] Closures don't seem to work properly when referring to the iteration variable in DOLIST, DOTIMES, DO and LOOP. [3-10] What is the difference between FUNCALL and APPLY? [3-11] Miscellaneous things to consider when debugging code. [3-12] When is it right to use EVAL? [3-13] Why does my program's behavior change each time I use it? [3-14] When producing formatted output in Lisp, where should you put the newlines (e.g., before or after the line, FRESH-LINE vs TERPRI, ~& vs ~% in FORMAT)? [3-15] I'm using DO to do some iteration, but it doesn't terminate. [3-16] My program works when interpreted but not when compiled! Lisp Implementations and Mailing Lists (Part 4): [4-0] Free Common Lisp implementations. [4-1] Commercial Common Lisp implementations. [4-1a] Lisp-to-C translators [4-2] Scheme Implementations [4-4] Free Implementations of Other Lisp Dialects [4-5] Commercial Implementations of Other Lisp Dialects [4-6] What is Dylan? [4-7] What is Pearl Common Lisp? [4-9] What Lisp-related discussion groups and mailing lists exist? [4-10] ANSI Common Lisp -- Where can I get a copy of the draft standard? Object-oriented Programming in Lisp (Part 5): [5-0] What is CLOS (PCL) and where can I get it? How do you pronounce CLOS? What is the Meta-Object Protocol (MOP)? [5-1] What documentation is available about object-oriented programming in Lisp? [5-2] How do I write a function that can access defstruct slots by name? I would like to write something like (STRUCTURE-SLOT <object> '<slot-name>). [5-3] How can I list all the CLOS instances in a class? [5-4] How can I store data and CLOS instances (with possibly circular references) on disk so that they may be retrieved at some later time? (Persistent Object Storage) [5-5] Given the name of a class, how can I get the names of its slots? [5-6] Free CLOS software. FTP Resources (Part 6): [6-0] General information about FTP Resources for Lisp [6-1] Repositories of Lisp Software [6-3] Publicly Redistributable Lisp Software [6-6] Formatting code in LaTeX (WEB and other literate programming tools) [6-7] Where can I get an implementation of Prolog in Lisp? [6-8] World-Wide Web (WWW) Resources Lisp Window Systems and GUIs (Part 7): [7-1] How can I use the X Window System or other GUIs from Lisp? [7-2] What Graphers/Browsers are available? Search for \[#\] to get to question number # quickly. *** Recent Changes: ;;; 1.48: ;;; 13-JUL-94 mk Updated Marlais entry in part 4. ;;; 14-JUL-94 mk Updated DTP entry in part 6. ;;; 14-JUL-94 mk Added entry on Lisp2Wish to part 7. ;;; 15-JUL-94 mk Updated WCL entry (version 2.2 for solaris). ;;; 21-JUL-94 mk Expanded ILU entry in part 6. ;;; 22-JUL-94 mk Updated the Common Lisp Repository entry with information ;;; about the Prime Time Freeware for AI CD-ROM publication, ;;; keyword searching, etc., etc., etc. ;;; 11-AUG-94 mk Added ftp site for source code to Graham's "On Lisp" book. ;;; 12-AUG-94 mk Lisp-Jobs mailing list has moved. ;;; 12-AUG-94 mk Added amiga-lisp mailing list to [4-9]. ;;; ;;; 1.49: ;;; 23-AUG-94 mk Moved the lisp-faq mailing list (for maintenance of the ;;; FAQ) from think.com to ai+lisp-faq@cs.cmu.edu. ;;; FAQ no longer available from ftp.think.com. ;;; 23-AUG-94 mk Digital Press is now owned by Butterworth-Heinemann, ;;; and their new address is: ;;; Digital Press, 80 Montvale Avenue, Stoneham, MA 02180 ;;; Tel: 800-366-2665 (617-438-8464), Fax: 617-297-4851. ;;; 26-AUG-94 mk Updated ILISP entry in [2-1]. ;;; 26-AUG-94 mk Added entry on JLISP to [4-4]. ;;; 29-AUG-94 mk CLtL2 now available by anonymous FTP, courtesy of ;;; Butterworth-Heinemann, the new owners of Digital Press. ;;; 30-AUG-94 mk Numbers for Digital Press have changed. They are now ;;; Tel: 800-366-2665 (USA) or 617-928-2500 ;;; Fax: 800-446-6520 (USA) or 617-933-6333 ;;; 8-SEP-94 mk Corrected expansion for SC22/WG16 in [1-6] glossary. ;;; ;;; 1.50: ;;; 14-SEP-94 mk Improved IDEAL entry in [6-3]. *** Introduction: Certain questions and topics come up frequently in the various network discussion groups devoted to and related to Lisp. This file/article is an attempt to gather these questions and their answers into a convenient reference for Lisp programmers. It (or a reference to it) is posted periodically. The hope is that this will cut down on the user time and network bandwidth used to post, read and respond to the same questions over and over, as well as providing education by answering questions some readers may not even have thought to ask. This is not a Lisp tutorial, nor is it an exhaustive list of all Lisp intricacies. Lisp is a very powerful and expressive language, but with that power comes many complexities. This list attempts to address the ones that average Lisp programmers are likely to encounter. If you are new to Lisp, see the answer to the question "How can I learn Lisp?". The latest version of this FAQ is available via anonymous FTP from CMU: To obtain the files from CMU, connect by anonymous FTP to ftp.cs.cmu.edu:/user/ai/pubs/faqs/lisp/ [128.2.206.173] using username "anonymous" and password "name@host" (substitute your email address) or via AFS in the Andrew File System directory /afs/cs.cmu.edu/project/ai-repository/ai/pubs/faqs/lisp/ and get the files lisp_1.faq, lisp_2.faq, lisp_3.faq, lisp_4.faq, lisp_5.faq, lisp_6.faq and lisp_7.faq. You can also obtain a copy of the FAQ by sending a message to ai+query@cs.cmu.edu with Send Lisp FAQ in the message body. The FAQ postings are also archived in the periodic posting archive on rtfm.mit.edu:/pub/usenet/news.answers/lisp-faq/ [18.181.0.24] If you do not have anonymous ftp access, you can access the archive by mail server as well. Send an E-mail message to mail-server@rtfm.mit.edu with "help" and "index" in the body on separate lines for more information. An automatically generated HTML version of the Lisp FAQ is accessible by WWW as part of the AI-related FAQs Mosaic page. The URL for this resource is http://www.cs.cmu.edu:8001/Web/Groups/AI/html/faqs/top.html The direct URL for the Lisp FAQ is http://www.cs.cmu.edu:8001/Web/Groups/AI/html/faqs/lang/lisp/top.html Unless otherwise specified, the Lisp dialect referred to is Common Lisp, as defined by "Common Lisp: the Language" (aka "CLtL1") as well as corrections (but not enhancements) from "Common Lisp: the Language, 2nd Edition" (aka "CLtL2"), both by Guy L. Steele, Jr. and published by Digital Press. Note that CLtL2 is NOT an official specification for the language; ANSI Committee X3J13 is preparing such a specification. See question [4-10] for information on the status of the ANSI specification for Common Lisp. Enhancements such as CLOS, conditions, and the LOOP macro will be referred to separately. If you need to cite the FAQ for some reason, use the following format: Mark Kantrowitz and Barry Margolin, "Answers to Frequently Asked Questions about Lisp", comp.lang.lisp, <month>, <year>, ftp.cs.cmu.edu:/user/ai/pubs/faqs/lisp/lisp_?.faq, ai+lisp-faq@cs.cmu.edu. ---------------------------------------------------------------- Subject: [1-0] What is the purpose of this newsgroup? The newsgroup comp.lang.lisp exists for general discussion of topics related to the programming language Lisp. For example, possible topics can include (but are not necessarily limited to): announcements of Lisp books and products discussion of programs and utilities written in Lisp discussion of portability issues questions about possible bugs in Lisp implementations problems porting an implementation to some architecture Postings should be of general interest to the Lisp community. See also question [4-9]. Postings asking for solutions to homework problems are inappropriate. Every so often, somebody posts an inflammatory message, such as My programming language is better than yours (Lisp vs. C/Prolog/Scheme). Loop (or Series) should/shouldn't be part of the language. These "religious" issues serve no real purpose other than to waste bandwidth. If you feel the urge to respond to such a post, please do so through a private e-mail message. Questions about object oriented programming in Lisp should be directed to the newsgroup comp.lang.clos. Similarly, questions about the programming language Scheme should be directed to the newsgroup comp.lang.scheme. Discussion of functional programming language issues should be directed to the newsgroup comp.lang.functional. Discussion of AI programs implemented in Lisp should sometimes be cross-posted to the newsgroup comp.ai. ---------------------------------------------------------------- Subject: [1-1] What is the difference between Scheme and Common Lisp? Scheme is a dialect of Lisp that stresses conceptual elegance and simplicity. It is specified in R4RS and IEEE standard P1178. (See the Scheme FAQ for details on standards for Scheme.) Scheme is much smaller than Common Lisp; the specification is about 50 pages, compared to Common Lisp's 1300 page draft standard. (See question [4-10] for details on standards for Common Lisp.) Advocates of Scheme often find it amusing that the Scheme standard is shorter than the index to CLtL2. Scheme is often used in computer science curricula and programming language research, due to its ability to represent many programming abstractions with its simple primitives. Common Lisp is often used for real world programming because of its large library of utility functions, a standard object-oriented programming facility (CLOS), and a sophisticated condition handling system. See the Scheme FAQ for information about object-oriented programming in Scheme. In Common Lisp, a simple program would look something like the following: (defun fact (n) (if (< n 2) 1 (* n (fact (1- n))))) In Scheme, the equivalent program would like like this: (define fact (lambda (n) (if (< n 2) 1 (* n (fact (- n 1)))))) Experienced Lisp programmers might write this program as follows in order to allow it to run in constant space: (defun fact (n) (labels ((tail-recursive-fact (counter accumulator) (if (> counter n) accumulator (tail-recursive-fact (1+ counter) (* counter accumulator))))) (tail-recursive-fact 1 1))) Whereas in Scheme the same computation could be written as follows: (define fact (lambda (n) (letrec ((tail-recursive-fact (lambda (counter accumulator) (if (> counter n) accumulator (tail-recursive-fact (+ counter 1) (* counter accumulator)))))) (tail-recursive-fact 1 1)))) or perhaps (using IEEE named LETs): (define fact (lambda (n) (let loop ((counter n) (accumulator 1)) (if (< counter 2) accumulator (loop (- counter 1) (* accumulator counter)))))) Some Schemes allow one to use the syntax (define (fact n) ...) instead of (define fact (lambda (n) ...)). ---------------------------------------------------------------- Subject: [1-2] Lisp books, introductions, documentation, periodicals, journals, and conference proceedings. There are several good Lisp introductions and tutorials: 1. David S. Touretzky "Common Lisp: A Gentle Introduction to Symbolic Computation" Benjamin/Cummings Publishers, Redwood City, CA, 1990. 592 pages. ISBN 0-8053-0492-4. Perhaps the best tutorial introduction to the language. It has clear and correct explanations, and covers some fairly advanced topics. The book is an updated Common Lisp version of the 1984 edition published by Harper and Row Publishers. Three free Lisp educational tools which were used in the book -- Evaltrace, DTRACE and SDRAW -- are available by anonymous ftp from b.gp.cs.cmu.edu:/usr/dst/public/lisp/ b.gp.cs.cmu.edu:/usr/dst/public/evaltrace/ Evaltrace is a graphical notation for explaining how evaluation works and is described in "Visualizing Evaluation in Applicative Languages" by David S. Touretzky and Peter Lee, CACM 45-59, October 1992. DTRACE is a "detailed trace" which provides more information than the tracing tools provided with most Common Lisp implementations. SDRAW is a read-eval-draw loop that evaluates Lisp expressions and draws the result as a cons cell diagram (for both X11 and ascii terminals). Also available is PPMX, a tool for pretty printing macro expansions. 2. Robert Wilensky "Common LISPcraft" W. W. Norton, 1986. 500 pages. ISBN 0-393-95544-3. 3. Wade L. Hennessey "Common Lisp" McGraw-Hill, 1989. 395 pages. Fairly good, but jumps back and forth from the simple to the complex rather quickly, with no clear progression in difficulty. 4. Laurent Siklossy "Let's Talk LISP" Prentice-Hall, NJ, 1976. 237 pages. Good introduction, but quite out of date. 5. Stuart C. Shapiro "Common Lisp: An Interactive Approach" Computer Science Press/W.H. Freeman, New York, 1992. ISBN 0-7167-8218-9 The errata for the book may be obtained by anonymous ftp from ftp.cs.buffalo.edu:/users/shapiro/clerrata.ps Other introductions to Lisp include: 1. A. A. Berk. "LISP, The Language of Artificial Intelligence" Van Nostrand Reinhold, 1985. 160 pages. 2. Paul Y. Gloess. "An Alfred handy guide to Understanding LISP" Alfred Publishers (Sherman Oaks, CA), 1982. 64 pages. 3. Ward D. Maurer. "The Programmer's Introduction to LISP" American Elsevier, 1972. 112 pages. 4. Hank Bromley and Richard Lamson. "LISP Lore: A Guide to Programming the LISP Machine" Kluwer Academic (Boston), 1987. 337 pages. 5. Sharam Hekmatpour. "Introduction to LISP and Symbol Manipulation" Prentice Hall (New York), 1988. 303 pages. 6. Deborah G. Tatar "A programmer's guide to Common Lisp" Digital Press, 1987. 327 pages. ISBN 0-932376-87-8. Good introduction on Common Lisp for programmers familiar with other programming languages, such as FORTRAN, PASCAL, or C. 7. Timothy Koschmann "The Common Lisp Companion" John Wiley & Sons, 1990. ISBN 0-471-503-8-8. Targeted for those with some programming experience who wish to learn draft-ANSI Common Lisp, including CLOS and the CL condition system. Examples progress incrementally from simple numerical calculation all the way to a logic-programming extension to CL. More advanced introductions to Lisp and its use in Artificial Intelligence include: 1. Peter Norvig. "Paradigms of AI Programming: Case Studies in Common Lisp" Morgan Kaufmann, 1992. 946 pages. ISBN 1-55860-191-0. $49.95. Provides an in-depth exposition of advanced AI programming techniques and includes large-scale detailed examples. The book is the most advanced AI/Common-Lisp programming text and reference currently available, and hence is not for the complete novice. It focuses on the programming techniques necessary for building large AI systems, including object-oriented programming, and has a strong performance orientation. The text is marked by its use of "non-toy" examples to illustrate the techniques. All of the examples are written in Common Lisp, and copies of the source code are available by anonymous ftp from unix.sri.com:/pub/norvig and on disk in Macintosh or DOS format from the publisher. Some of the techniques described include rule-based pattern matching (GPS, Eliza, a subset of Macsyma, the Emycin expert system shell), constraint propagation and backtracking (Waltz line-labelling), alpha-beta search (Othello), natural language processing (top-down, bottom-up and chart parsing), logic-programming (unification and Prolog), interpreters and compilers for Scheme, and object-oriented programming (CLOS). The examples are also used to illustrate good programming style and efficiency. There is a guide to trouble-shooting and debugging Lisp programs, a style guide, and a discussion of portability problems. Some of the efficiency techniques described include memoization, data indexing, compilation, delaying computation, proper use of declarations, avoiding garbage collection, and choosing and using the correct data structure. The book also serves as an advanced introduction to Common Lisp, with sections on the Loop macro, CLOS and sequences, and some coverage of error handling, series, and the package facility. 2. Eugene Charniak, Christopher K. Riesbeck, Drew V. McDermott and James R. Meehan. "Artificial Intelligence Programming", 2nd edition. Lawrence Erlbaum Associates (Hillsdale, NJ), 1987. 533 pages. Provides many nice code fragments, all of which are written in Common Lisp. The first half of the book covers topics like macros, the reader, data structures, control structures, and defstructs. The second half of the book describes programming techniques specific to AI, such as discrimination nets, production systems, deductive database retrieval, logic programming, and truth maintenance. 3. Patrick H. Winston and Berthold K. P. Horn. "LISP", 3rd edition. Addison-Wesley (Reading, MA), 1989. 611 pages. ISBN 0-201-08319-1 Covers the basic concepts of the language, but also gives a lot of detail about programming AI topics such as rule-based expert systems, forward chaining, interpreting transition trees, compiling transition trees, object oriented programming, and finding patterns in images. Not a tutorial. Has many good examples. Source code for the examples is available by anonymous ftp from ftp.ai.mit.edu:/pub/lisp3/. (The code runs in Lucid, Allegro, KCL, GCLisp, MCL, Symbolics Genera. Send mail with subject line "help" to ai3@ai.mit.edu for more information.) 4. John R. Anderson, Albert T. Corbett, and Brian J. Reiser. "Essential LISP" Addison-Wesley (Reading, MA), 1987. 352 pages. Concentrates on how to use Lisp with iteration and recursion. 5. Robert D. Cameron and Anthony H. Dixon "Symbolic Computing with Lisp" Prentice-Hall, 1992, 326 pages. ISBN 0-13-877846-9. The book is intended primarily as a third-year computer science text. In terms of programming techniques, it emphasizes recursion and induction, data abstraction, grammar-based definition of Lisp data structures and functional programming style. It uses two Lisp languages: (1) a purely functional subset of Lisp called Small Lisp and (2) Common Lisp. An MS-DOS interpreter for Small Lisp (including source) is provided with the book. It considers applications of Lisp to formal symbolic data domains: algebraic expressions, logical formulas, grammars and programming languages. 6. Hasemer and Domingue. "Common Lisp Programming for Artificial Intelligence" Addison-Wesley, 1989. 7. Steven Tanimoto "The Elements of Artificial Intelligence: An Introduction Using Lisp" Computer Science Press, Rockville, MD, 1987, 530 pages. 8. Patrick R. Harrison "Common Lisp and Artificial Intelligence" Prentice Hall, Englewood Clifs, NJ, 1990. 244 pages. ISBN 0-13-155243. 9. Paul Graham "On Lisp: Advanced Techniques for Common Lisp" Prentice Hall, Englewood Clifs, NJ, 1994. 400 pages, ISBN 0-13-030552-9. Emphasizes a bottom-up style of writing programs, which he claims is natural in Lisp and has advantages over the traditional way of writing programs in C and Pascal. Also has in-depth sections on writing macros with several nice examples. Source code is available by anonymous ftp from endor.harvard.edu:/pub/onlisp/ as a single 56kb file. General Lisp reference books include: 1. Guy L. Steele "Common Lisp: The Language" [CLtL1] Digital Press, 1984. 465 pages. ISBN 0-932376-41-X. 2. Guy L. Steele "Common Lisp: The Language, 2nd Edition" [CLtL2] Digital Press, 1990. 1029 pages, ISBN 1-55558-041-6 paperbound ($39.95). [Butterworth-Heinemann, the owners of Digital Press, have made the LaTeX sources to this book available by anonymous FTP from cambridge.apple.com:/pub/CLTL/ A copy of the distribution is also available from ftp.cs.cmu.edu:/user/ai/lang/lisp/doc/cltl/ The paperbound version of the book is, of course, available at fine bookstores, or contact them directly at Digital Press, 80 Montvale Avenue, Stoneham, MA 02180, call 800-366-2665 (617-928-2500), or fax 800-446-6520 (617-933-6333). A copy of the Digital Press book catalog is available from the same FTP location.] A html version, produces using latex2html on the latex sources, is accessible via the URL: http://www.dcs.gla.ac.uk/~alison/clm/clm.html 3. Franz Inc. "Common Lisp: The Reference" Addison-Wesley, Reading, MA 1988. ISBN 0-201-11458-5 Entries on Lisp (CLtL1) functions in alphabetical order. Lisp periodicals include: 1. LISP Pointers. Published by ACM SIGPLAN six times a year. Volume 1, Number 1 was April-May 1987. Subscriptions: ACM Members $12; ACM Student Members $7; Non-ACM members $25. Mail checks payable to the ACM to ACM Inc., PO Box 12115, Church Street Station, New York, NY 10249. 2. LISP and Symbolic Computation, Kluwer Academic Press. Volume 1 was published in 1989. (jlz@lucid.com is the editor). ISSN 0892-4635. Subscriptions: Institutions $169; Individuals $80. Add $8 for air mail. Kluwer Academic Publishers, PO Box 322, 3300 AH Dordrecht, The Netherlands, or Kluwer Academic Publishers, PO Box 358, Accord Station, Hingham, MA 02018-0358. A full table of contents of all published issues, aims and scope, and instructions for authors are available by anonymous ftp from ftp.std.com:/Kluwer/journals/ as the files lisp.toc and lisp.inf. 3. Proceedings of the biannual ACM Lisp and Functional Programming Conference. (First one was in 1980.) 4. Proceedings of the annual Lisp Users and Vendors Conference. Implementation-specific questions: 1. Lucid. See the wizards.doc file that comes with the Lucid release. It describes functions, macros, variables and constants that are not official parts of the product and are not supported. Constructs described in this file include: the interrupt facility, the source file recording facility, the resource facility, multitasking, writing your own streams, lisp pipes, i/o buffers, the compiler, floating-point functions, memory management, debugger information, the window tool kit, extensions to the editor, the foreign function interface, clos information, delivery toolkit information, and Lucid lisp training classes. The wizards.doc file also covers i/o constructs, functions for dealing with DEFSTRUCT, functions and constants for dealing with procedure objects, functions and constants for dealing with code objects, function for mapping objects, additional keyword argument to DISKSAVE, function used in the implementation of arrays, function for monitor-specific behavior for a process, additional keyword argument to RUN-PROGRAM, and load-time evaluation. Many books on Scheme are worth reading even if you use Common Lisp, because many of the issues are similar. Scheme is a simpler language to learn, so it is often used in introductory computer science classes. See the Scheme FAQ for a list of introductions and references for Scheme. The two key introductions are Abelson and Sussman's "Structure and Interpretation of Computer Programs" and Friedman and Felleisen's "The Little LISPer". Special Topics: Garbage Collection: Wilson, Paul R., "Uniprocessor Garbage Collection Techniques" Proceedings of the 1992 International Workshop on Memory Management. Springer Lecture Notes #637. Surveys garbage collection techniques. Includes an excellent bibliography. Available by anonymous ftp from cs.utexas.edu:/pub/garbage/gcsurvey.ps. The BibTeX format of the bibliography is also available in this directory, along with several other papers. Contact wilson@cs.utexas.edu for more info. ---------------------------------------------------------------- Subject: [1-3] How can I improve my Lisp programming style and coding efficiency? There are several books about Lisp programming style, including: 1. Molly M. Miller and Eric Benson "Lisp Style and Design" Digital Press, 1990. 214 pages. ISBN 1-55558-044-0. How to write large Lisp programs and improve Lisp programming style. Uses the development of Lucid CL as an example. 2. Robin Jones, Clive Maynard, and Ian Stewart. "The Art of Lisp Programming" Springer-Verlag, 1989. 169 pages. 3. W. Richard Stark. "LISP, Lore, and Logic: An Algebraic View of LISP Programming, Foundations, and Applications" Springer-Verlag, 1990. 278 pages. ISBN 0-387-97072-X paper ($42). Self-modifying code, self-reproducing programs, etc. 4. CMU CL User's Manual, Chapter 7, (talks about writing efficient code). It is available by anonymous ftp from any CMU CS machine (e.g., ftp.cs.cmu.edu [128.2.206.173]) as the file /afs/cs.cmu.edu/project/clisp/docs/cmu-user/cmu-user.ps [when getting this file by anonymous ftp, one must cd to the directory in one atomic operation, as some of the superior directories on the path are protected from access by anonymous ftp.] 5. See also Norvig's book, SICP (Abelson & Sussman), SAP (Springer and Friedman). 6. Hallvard Tretteberg's Lisp Style Guide is available by anonymous ftp in ftp.think.com:/public/think/lisp/style-guide.text. There is a fair bit of overlap between Hallvard's style guide and the notes below and in part 3 of this FAQ. 7. Rajeev Sangal "Programming Paradigms in Lisp" McGraw-Hill, 1991. ISBN 0-07-054666-5. 8. Rodney A. Brooks. "Programming in Common Lisp" John Wiley & Sons, New York, 1985. 303 pages. ISBN 0-471-81888-7. Chapter 5 discusses Lisp programming style. Here are some general suggestions/notes about improving Lisp programming style, readability, correctness and efficiency: General Programming Style Rules: - Write short functions, where each function provides a single, well-defined operation. Small functions are easier to read, write, test, debug, and understand. - Use descriptive variable and function names. If it isn't clear from the name of a function or variable what its purpose is, document it with a documentation string and a comment. In fact, even if the purpose is evident from the name, it is still worth documenting your code. - Don't write Pascal (or C) code in Lisp. Use the appropriate predefined functions -- look in the index to CLtL2, or use the APROPOS and DESCRIBE functions. Don't put a close parenthesis on a line by itself -- this can really aggravate programmers who grew up on Lisp. Lisp-oriented text editors include tools for ensuring balanced parentheses and for moving across pairs of balanced parentheses. You don't need to stick comments on close parentheses to mark which expression they close. - Use proper indentation -- you should be able to understand the structure of your definitions without noticing the parentheses. In general, the way one indents a form is controlled by the first symbol of the form. In DEFUNs, for example, one puts the symbol DEFUN, the function name, and the argument list all on the same line. If the argument list is too long, one can break it at one of the lambda keywords. Following the argument list, one inserts a carriage return and lists the expressions in the body of the definition, with each form starting on its own line indented three spaces relative to the open parenthesis of the parent (in this case the DEFUN). This general style -- of putting all the significant elements of a form on a single line, followed by a carriage return and the indented body -- holds for many Lisp constructs. There are, of course, variations, such as keeping the first clause on the same line as the COND or CASE symbol, and the rules are relaxed in different ways to keep line lengths to a manageable size. If you find yourself having trouble fitting everything in even with line breaking and relaxing the rules, either your function names are too long or your code isn't very modular. You should perceive this as a signal that you need to break up your big definitions into smaller chunks, each with a clearly defined purpose, and possibly replace long function names with concise but apt shorter ones. - Use whitespace appropriately. Use whitespace to separate semantically distinct code segments, but don't use too much whitespace. For example, GOOD: (defun foo (x y) (let ((z (+ x y 10))) (* z z))) BAD: (defun foo(x y)(let((z(+ x y 10)))(* z z))) (defun foo ( x y ) (let ( ( z (+ x y 10) ) ) ( * z z ) ) ) Although the Lisp reader and compiler don't care which you use, most experienced Lisp programs find the first example much easier to read than the last two. - Don't use line lengths greater than 80 characters. People who write code using Zmacs on Symbolics Lisp Machines are notoriously guilty of violating this rule, because the CPT6 font allows one to squeeze a tremendous amount of code on the display, especially if one spreads the code out horizontally. This makes it more difficult to read when printed out or read on an 80x24 xterm window. In fact, use a line length of 72 characters because it leaves a strip of white space at the edge of the window. The following functions often abused or misunderstood by novices. Think twice before using any of these functions. - EVAL. Novices almost always misuse EVAL. When experts use EVAL, they often would be better off using APPLY, FUNCALL, or SYMBOL-VALUE. Use of EVAL when defining a macro should set off a warning bell -- macro definitions are already evaluated during expansion. See also the answer to question 3-12. The general rule of thumb about EVAL is: if you think you need to use EVAL, you're probably wrong. - PROGV. PROGV binds dynamic variables and is often misused in conjunction with EVAL, which uses the dynamic environment. In general, avoid unnecessary use of special variables. PROGV is mainly for writing interpreters for languages embedded in Lisp. If you want to bind a list of values to a list of lexical variables, use (MULTIPLE-VALUE-BIND (..) (VALUES-LIST ..) ..) or (MULTIPLE-VALUE-SETQ (..) (VALUES-LIST ..)) instead. Most decent compilers can optimize this expression. However, use of this idiom is not to be encouraged unless absolutely necessary. - CATCH and THROW. Often a named BLOCK and RETURN-FROM are more appropriate. Use UNWIND-PROTECT when necessary. - Destructive operations, such as NCONC, SORT, DELETE, RPLACA, and RPLACD, should be used carefully and sparingly. In general, trust the garbage collector: allocate new data structures when you need them. To improve the readability of your code, - Don't use any C{A,D}R functions with more than two letters between the C and the R. When nested, they become hard to read. If you have complex data structures, you are often better off describing them with a DEFSTRUCT, even if the type is LIST. The data abstraction afforded by DEFSTRUCT makes the code much more readable and its purpose clearer. If you must use C{A,D}R, try to use DESTRUCTURING-BIND instead, or at least SECOND, THIRD, NTH, NTHCDR, etc. - Use COND instead of IF and PROGN. In general, don't use PROGN if there is a way to write the code within an implicit PROGN. For example, (IF (FOO X) (PROGN (PRINT "hi there") 23) 34) should be written using COND instead. - Never use a 2-argument IF or a 3-argument IF with a second argument of NIL unless you want to emphasize the return value; use WHEN and UNLESS instead. You will want to emphasize the return value when the IF clause is embedded within a SETQ, such as (SETQ X (IF (EQ Y Z) 2 NIL)). If the second argument to IF is the same as the first, use OR instead: (OR P Q) rather than (IF P P Q). Use UNLESS instead of (WHEN (NOT ..) ..) but not instead of (WHEN (NULL ..) ..). - Use COND instead of nested IF statements. Be sure to check for unreachable cases, and eliminate those cond-clauses. - Use backquote, rather than explicit calls to LIST, CONS, and APPEND, whenever writing a form which produces a Lisp form, but not as a general substitute for LIST, CONS and APPEND. LIST, CONS and APPEND usually allocate new storage, but lists produced by backquote may involve destructive modification (e.g., ,.). - Make the names of special (global) variables begin and end with an asterisk (*): (DEFVAR *GLOBAL-VARIABLE*) Some programmers will mark the beginning and end of an internal global variable with a percent (%) or a period (.). Make the names of constants begin and end with a plus (+): (DEFCONSTANT +E+ 2.7182818) This helps distinguish them from lexical variables. Some people prefer to use macros to define constants, since this avoids the problem of accidentally trying to bind a symbol declared with defconstant. - If your program is built upon an underlying substrate which is implementation-dependent, consider naming those functions and macros in a way that visually identifies them, either by placing them in their own package, or prepending a character like a %, ., or ! to the function name. Note that many programmers use the $ as a macro character for slot access, so it should be avoided unless you're using it for that purpose. - Don't use property lists. Instead, use an explicit hash table. This helps avoid problems caused by the symbol being in the wrong package, accidental reuse of property keys from other programs, and allows you to customize the structure of the table. - Use the most specific construct that does the job. This lets readers of the code see what you intended when writing the code. For example, don't use SETF if SETQ will do (e.g., for lexical variables). Use the most specific predicate to test your conditions. If you intend for a function to be a predicate, have it return T for true, not just non-NIL. - When NIL is used as an empty list, use () in your code. When NIL is used as a boolean, use NIL. Similarly, use NULL to test for an empty list, NOT to test a logical value. Use ENDP to test for the end of a list, not NULL. - Don't use the &AUX lambda-list keyword. It is always clearer to define local variables using LET or LET*. - When using RETURN and RETURN-FROM to exit from a block, don't use (VALUES ..) when returning only one value, except if you are using it to suppress extra multiple values from the first argument. - If you want a function to return no values (i.e., equivalent to VOID in C), use (VALUES) to return zero values. This signals to the reader that the function is used mainly for side-effects. - (VALUES (VALUES 1 2 3)) returns only the first value, 1. You can use (VALUES (some-multiple-value-function ..)) to suppress the extra multiple values from the function. Use MULTIPLE-VALUE-PROG1 instead of PROG1 when the multiple values are significant. - When using MULTIPLE-VALUE-BIND and DESTRUCTURING-BIND, don't rely on the fact that NIL is used when values are missing. This is an error in some implementations of DESTRUCTURING-BIND. Instead, make sure that your function always returns the proper number of values. - Type the name of external symbols, functions, and variables from the COMMON-LISP package in uppercase. This will allow your code to work properly in a case-sensitive version of Common Lisp, since the print-names of symbols in the COMMON-LISP package are uppercase internally. (However, not everybody feels that being nice to case-sensitive Lisps is a requirement, so this isn't an absolute style rule, just a suggestion.) Lisp Idioms: - MAPCAN is used with a function to return a variable number of items to be included in an output list. When the function returns zero or one items, the function serves as a filter. For example, (mapcan #'(lambda (x) (when (and (numberp x) (evenp x)) (list x))) '(1 2 3 4 x 5 y 6 z 7)) Documentation: - Comment your code. Use three semicolons in the left margin before the definition for major explanations. Use two semicolons that float with the code to explain the routine that follows. Two semicolons may also be used to explain the following line when the comment is too long for the single semicolon treatment. Use a single semicolon to the right of the code to explain a particular line with a short comment. The number of semicolons used roughly corresponds with the length of the comment. Put at least one blank line before and after top-level expressions. - Include documentation strings in your code. This lets users get help while running your program without having to resort to the source code or printed documentation. Issues related to macros: - Never use a macro instead of a function for efficiency reasons. Declaim the function as inline -- for example, (DECLAIM (INLINE ..)) This is *not* a magic bullet -- be forewarned that inline expansions can often increase the code size dramatically. INLINE should be used only for short functions where the tradeoff is likely to be worthwhile: inner loops, types that the compiler might do something smart with, and so on. - When defining a macro that provides an implicit PROGN, use the &BODY lambda-list keyword instead of &REST. - Use gensyms for bindings within a macro, unless the macro lets the user explicitly specify the variable. For example: (defmacro foo ((iter-var list) body-form &body body) (let ((result (gensym "RESULT"))) `(let ((,result nil)) (dolist (,iter-var ,list ,result) (setq ,result ,body-form) (when ,result ,@body))))) This avoids errors caused by collisions during macro expansion between variable names used in the macro definition and in the supplied body. - Use a DO- prefix in the name of a macro that does some kind of iteration, WITH- when the macro establishes bindings, and DEFINE- or DEF- when the macro creates some definitions. Don't use the prefix MAP- in macro names, only in function names. - Don't create a new iteration macro when an existing function or macro will do. - Don't define a macro where a function definition will work just as well -- remember, you can FUNCALL or MAPCAR a function but not a macro. - The LOOP and SERIES macros generate efficient code. If you're writing a new iteration macro, consider learning to use one of them instead. File Modularization: - If your program involves macros that are used in more than one file, it is generally a good idea to put such macros in a separate file that gets loaded before the other files. The same things applies to primitive functions. If a macro is complicated, the code that defines the macro should be put into a file by itself. In general, if a set of definitions form a cohesive and "independent" whole, they should be put in a file by themselves, and maybe even in their own package. It isn't unusual for a large Lisp program to have files named "site-dependent-code", "primitives.lisp", and "macros.lisp". If a file contains primarily macros, put "-macros" in the name of the file. Stylistic preferences: - Use (SETF (CAR ..) ..) and (SETF (CDR ..) ..) in preference to RPLACA and RPLACD. Likewise (SETF (GET ..) ..) instead of PUT. - Use INCF, DECF, PUSH and POP instead instead of the corresponding SETF forms. - Many programmers religiously avoid using CATCH, THROW, BLOCK, PROG, GO and TAGBODY. Tags and go-forms should only be necessary to create extremely unusual and complicated iteration constructs. In almost every circumstance, a ready-made iteration construct or recursive implementation is more appropriate. - Don't use LET* where LET will do. Don't use LABELS where FLET will do. Don't use DO* where DO will do. - Don't use DO where DOTIMES or DOLIST will do. - If you like using MAPCAR instead of DO/DOLIST, use MAPC when no result is needed -- it's more efficient, since it doesn't cons up a list. If a single cumulative value is required, use REDUCE. If you are seeking a particular element, use FIND, POSITION, or MEMBER. - If using REMOVE and DELETE to filter a sequence, don't use the :test-not keyword or the REMOVE-IF-NOT or DELETE-IF-NOT functions. Use COMPLEMENT to complement the predicate and the REMOVE-IF or DELETE-IF functions instead. - Use complex numbers to represent points in a plane. - Don't use lists where vectors are more appropriate. Accessing the nth element of a vector is faster than finding the nth element of a list, since the latter requires pointer chasing while the former requires simple addition. Vectors also take up less space than lists. Use adjustable vectors with fill-pointers to implement a stack, instead of a list -- using a list continually conses and then throws away the conses. - When adding an entry to an association list, use ACONS, not two calls to CONS. This makes it clear that you're using an alist. - If your association list has more than about 10 entries in it, consider using a hash table. Hash tables are often more efficient. (See also [2-2].) - When you don't need the full power of CLOS, consider using structures instead. They are often faster, take up less space, and easier to use. - Use PRINT-UNREADABLE-OBJECT when writing a print-function. - Use WITH-OPEN-FILE instead of OPEN and CLOSE. - When a HANDLER-CASE clause is executed, the stack has already unwound, so dynamic bindings that existed when the error occured may no longer exist when the handler is run. Use HANDLER-BIND if you need this. - When using CASE and TYPECASE forms, if you intend for the form to return NIL when all cases fail, include an explicit OTHERWISE clause. If it would be an error to return NIL when all cases fail, use ECASE, CCASE, ETYPECASE or CTYPECASE instead. - Use local variables in preference to global variables whenever possible. Do not use global variables in lieu of parameter passing. Global variables can be used in the following circumstances: * When one function needs to affect the operation of another, but the second function isn't called by the first. (For example, *load-pathname* and *break-on-warnings*.) * When a called function needs to affect the current or future operation of the caller, but it doesn't make sense to accomplish this by returning multiple values. * To provide hooks into the mechanisms of the program. (For example, *evalhook*, *, /, and +.) * Parameters which, when their value is changed, represent a major change to the program. (For example, *print-level* and *print-readably*.) * For state that persists between invocations of the program. Also, for state which is used by more than one major program. (For example, *package*, *readtable*, *gensym-counter*.) * To provide convenient information to the user. (For example, *version* and *features*.) * To provide customizable defaults. (For example, *default-pathname-defaults*.) * When a value affects major portions of a program, and passing this value around would be extremely awkward. (The example here is output and input streams for a program. Even when the program passes the stream around as an argument, if you want to redirect all output from the program to a different stream, it is much easier to just rebind the global variable.) - Beginning students, especially ones accustomed to programming in C, Pascal, or Fortran, tend to use global variables to hold or pass information in their programs. This style is considered ugly by experienced Lisp programmers. Although assignment statements can't always be avoided in production code, good programmers take advantage of Lisp's functional programming style before resorting to SETF and SETQ. For example, they will nest function calls instead of using a temporary variable and use the stack to pass multiple values. When first learning to program in Lisp, try to avoid SETF/SETQ and their cousins as much as possible. And if a temporary variable is necessary, bind it to its first value in a LET statement, instead of letting it become a global variable by default. (If you see lots of compiler warnings about declaring variables to be special, you're probably making this mistake. If you intend a variable to be global, it should be defined with a DEFVAR or DEFPARAMETER statement, not left to the compiler to fix.) Correctness and efficiency issues: - In CLtL2, IN-PACKAGE does not evaluate its argument. Use defpackage to define a package and declare the external (exported) symbols from the package. - The ARRAY-TOTAL-SIZE-LIMIT may be as small as 1024, and the CALL-ARGUMENTS-LIMIT may be as small as 50. - Novices often mistakenly quote the conditions of a CASE form. For example, (case x ('a 3) ..) is incorrect. It would return 3 if x were the symbol QUOTE. Use (case x (a 3) ..) instead. - Avoid using APPLY to flatten lists. Although (apply #'append list-of-lists) may look like a call with only two arguments, it becomes a function call to APPEND, with the LIST-OF-LISTS spread into actual arguments. As a result it will have as many arguments as there are elements in LIST-OF-LISTS, and hence may run into problems with the CALL-ARGUMENTS-LIMIT. Use REDUCE or MAPCAN instead: (reduce #'append list-of-lists :from-end t) (mapcan #'copy-list list-of-lists) The second will often be more efficient (see note below about choosing the right algorithm). Beware of calls like (apply f (mapcar ..)). - NTH must cdr down the list to reach the elements you are interested in. If you don't need the structural flexibility of lists, try using vectors and the ELT function instead. - CASE statements can be vectorized if the keys are consecutive numbers. Such CASE statements can still have OTHERWISE clauses. To take advantage of this without losing readability, use #. with symbolic constants: (eval-when (compile load eval) (defconstant RED 1) (defconstant GREEN 2) (defconstant BLUE 3)) (case color (#.RED ...) (#.GREEN ...) (#.BLUE ...) ...) - Don't use quoted constants where you might later destructively modify them. For example, instead of writing '(c d) in (defun foo () (let ((var '(c d))) ..)) write (list 'c 'd) instead. Using a quote here can lead to unexpected results later. If you later destructively modify the value of var, this is self-modifying code! Some Lisp compilers will complain about this, since they like to make constants read-only. Modifying constants has undefined results in ANSI CL. See also the answer to question [3-13]. Similarly, beware of shared list structure arising from the use of backquote. Any sublist in a backquoted expression that doesn't contain any commas can share with the original source structure. - Don't proclaim unsafe optimizations, such as (proclaim '(optimize (safety 0) (speed 3) (space 1))) since this yields a global effect. Instead, add the optimizations as local declarations to small pieces of well-tested, performance-critical code: (defun well-tested-function () (declare (optimize (safety 0) (speed 3) (space 1))) ..) Such optimizations can remove run-time type-checking; type-checking is necessary unless you've very carefully checked your code and added all the appropriate type declarations. - Some programmers feel that you shouldn't add declarations to code until it is fully debugged, because incorrect declarations can be an annoying source of errors. They recommend using CHECK-TYPE liberally instead while you are developing the code. On the other hand, if you add declarations to tell the compiler what you think your code is doing, the compiler can then tell you when your assumptions are incorrect. Declarations also make it easier for another programmer to read your code. - Declaring the type of variables to be FIXNUM does not necessarily mean that the results of arithmetic involving the fixnums will be a fixnum; it could be a BIGNUM. For example, (declare (type fixnum x y)) (setq z (+ (* x x) (* y y))) could result in z being a BIGNUM. If you know the limits of your numbers, use a declaration like (declare (type (integer 0 100) x y)) instead, since most compilers can then do the appropriate type inference, leading to much faster code. - Don't change the compiler optimization with an OPTIMIZE proclamation or declaration until the code is fully debugged and profiled. When first writing code you should say (declare (optimize (safety 3))) regardless of the speed setting. - Depending on the optimization level of the compiler, type declarations are interpreted either as (1) a guarantee from you that the variable is always bound to values of that type, or (2) a desire that the compiler check that the variable is always bound to values of that type. Use CHECK-TYPE if (2) is your intention. - If you get warnings about unused variables, add IGNORE declarations if appropriate or fix the problem. Letting such warnings stand is a sloppy coding practice. To produce efficient code, - choose the right algorithm. For example, consider seven possible implementations of COPY-LIST: (defun copy-list (list) (let ((result nil)) (dolist (item list result) (setf result (append result (list item)))))) (defun copy-list (list) (let ((result nil)) (dolist (item list (nreverse result)) (push item result)))) (defun copy-list (list) (mapcar #'identity list)) (defun copy-list (list) (let ((result (make-list (length list)))) (do ((original list (cdr original)) (new result (cdr new))) ((null original) result) (setf (car new) (car original))))) (defun copy-list (list) (when list (let* ((result (list (car list))) (tail-ptr result)) (dolist (item (cdr list) result) (setf (cdr tail-ptr) (list item)) (setf tail-ptr (cdr tail-ptr)))))) (defun copy-list (list) (loop for item in list collect item)) (defun copy-list (list) (if (consp list) (cons (car list) (copy-list (cdr list))) list)) The first uses APPEND to tack the elements onto the end of the list. Since APPEND must traverse the entire partial list at each step, this yields a quadratic running time for the algorithm. The second implementation improves on this by iterating down the list twice; once to build up the list in reverse order, and the second time to reverse it. The efficiency of the third depends on the Lisp implementation, but it is usually similar to the second, as is the fourth. The fifth algorithm, however, iterates down the list only once. It avoids the extra work by keeping a pointer (reference) to the last cons of the list and RPLACDing onto the end of that. Use of the fifth algorithm may yield a speedup. Note that this contradicts the earlier dictum to avoid destructive functions. To make more efficient code one might selectively introduce destructive operations in critical sections of code. Nevertheless, the fifth implementation may be less efficient in Lisps with cdr-coding, since it is more expensive to RPLACD cdr-coded lists. Depending on the implementation of nreverse, however, the fifth and second implementations may be doing the same amount of work. The sixth example uses the Loop macro, which usually expands into code similar to the third. The seventh example copies dotted lists, and runs in linear time, but isn't tail-recursive. - use type declarations liberally in time-critical code, but only if you are a seasoned Lisp programmer. Appropriate type declarations help the compiler generate more specific and optimized code. It also lets the reader know what assumptions were made. For example, if you only use fixnum arithmetic, adding declarations can lead to a significant speedup. If you are a novice Lisp programmer, you should use type declarations sparingly, as there may be no checking to see if the declarations are correct, and optimized code can be harder to debug. Wrong declarations can lead to errors in otherwise correct code, and can limit the reuse of code in other contexts. Depending on the Lisp compiler, it may also be necessary to declare the type of results using THE, since some compilers don't deduce the result type from the inputs. - check the code produced by the compiler by using the disassemble function ---------------------------------------------------------------- Subject: [1-4] Where can I learn about implementing Lisp interpreters and compilers? Books about Lisp implementation include: 1. John Allen "Anatomy of Lisp" McGraw-Hill, 1978. 446 pages. ISBN 0-07-001115-X Discusses some of the fundamental issues involved in the implemention of Lisp. 2. Samuel Kamin "Programming Languages, An Interpreter-Based Approach" Addison-Wesley, Reading, Mass., 1990. ISBN 0-201-06824-9 Includes sources to several interpreters for Lisp-like languages, and a pointer to sources via anonymous ftp. Tim Budd reimplemented the interpreters in C++, and has made them available by anonymous ftp from cs.orst.edu:/pub/budd/kamin/ 3. Sharam Hekmatpour "Lisp: A Portable Implementation" Prentice Hall, 1985. ISBN 0-13-537490-X. Describes a portable implementation of a small dynamic Lisp interpreter (including C source code). 4. Peter Henderson "Functional Programming: Application and Implementation" Prentice-Hall (Englewood Cliffs, NJ), 1980. 355 pages. 5. Peter M. Kogge "The Architecture of Symbolic Computers" McGraw-Hill, 1991. ISBN 0-07-035596-7. Includes sections on memory management, the SECD and Warren Abstract Machines, and overviews of the various Lisp Machine architectures. 6. Daniel P. Friedman, Mitchell Wand, and Christopher T. Haynes "Essentials of Programming Languages" MIT Press, 1992, 536 pages. ISBN 0-262-06145-7. Teaches fundamental concepts of programming language design by using small interpreters as examples. Covers most of the features of Scheme. Includes a discussion of parameter passing techniques, object oriented languages, and techniques for transforming interpreters to allow their implementation in terms of any low-level language. Also discusses scanners, parsers, and the derivation of a compiler and virtual machine from an interpreter. Includes a few chapters on converting code into a continuation passing style. Source files available by anonymous ftp from cs.indiana.edu:/pub/eopl/ [129.79.254.191]. 7. Peter Lee, editor, "Topics in Advanced Language Implementation", The MIT Press, Cambridge, Mass., 1991. Articles relevant to the implementation of functional programming languages. 8. Also see the proceedings of the biannual ACM Lisp and Functional Programming conferences, the implementation notes for CMU Common Lisp, Norvig's book, and SICP (Abelson & Sussman). ---------------------------------------------------------------- Subject: [1-5] What is the "minimal" set of primitives needed for a Lisp interpreter? Many Lisp functions can be defined in terms of other Lisp functions. For example, CAAR can be defined in terms of CAR as (defun caar (list) (car (car list))) It is then natural to ask whether there is a "minimal" or smallest set of primitives necessary to implement the language. There is no single "best" minimal set of primitives; it all depends on the implementation. For example, even something as basic as numbers need not be primitive, and can be represented as lists. One possible set of primitives might include CAR, CDR, and CONS for manipulation of S-expressions, READ and PRINT for the input/output of S-expressions and APPLY and EVAL for the guts of an interpreter. But then you might want to add LAMBDA for functions, EQ for equality, COND for conditionals, SET for assignment, and DEFUN for definitions. QUOTE might come in handy as well. If you add more specialized datatypes, such as integers, floats, arrays, characters, and structures, you'll need to add primitives to construct and access each. AWKLisp is a Lisp interpreter written in awk, available by anonymous ftp from ftp.cs.cmu.edu:/user/ai/lang/lisp/impl/awk/. It has thirteen built-in functions: CAR, CDR, CONS, EQ, ATOM, SET, EVAL, ERROR, QUOTE, COND, AND, OR, LIST. A more practical notion of a "minimal" set of primitives might be to look at the implementation of Scheme. While many Scheme functions can be derived from others, the language is much smaller than Common Lisp. See Dybvig's PhD thesis, R. Kent Dybvig, "Three Implementation Models for Scheme", Department of Computer Science Technical Report #87-011, University of North Carolina at Chapel Hill, Chapel Hill, North Carolina, April 1987. for a justification of a particularly practical minimal set of primitives for Scheme. In a language like Common Lisp, however, there are a lot of low-level primitive functions that cannot be written in terms of the others, such as GET-UNIVERSAL-TIME, READ-CHAR, WRITE-CHAR, OPEN, and CLOSE, for starters. Moreover, real Common Lisp implementations are often built upon primitives that aren't part of the language, per se, and certainly not intended to be user-accessible, such as SYS:%POINTER-REF. Beside the references listed in [1-4], some other relevant references include: McCarthy, John, "Recursive Functions of Symbolic Expressions and their Computation by Machine, Part I", CACM 3(4):185-195, April 1960. [Defines five elementary functions on s-expressions.] McCarthy, John, "A Micro-Manual for Lisp -- not the whole Truth", ACM SIGPLAN Notices, 13(8):215-216, August 1978. [Defines the Lisp programming language in 10 rules and gives a small interpreter (eval) written in this Lisp.] McCarthy, John, et al., "LISP 1.5 Programmer's Manual", 2nd edition, MIT Press, 1965, ISBN 0-262-13011-4 (paperback). [Gives five basic functions, CAR, CDR, CONS, EQ, and ATOM. Using composition, conditional expressions (COND), and recursion, LAMBDA, and QUOTE, these basic functions may be used to construct the entire class of computable functions of S-expressions. Gives the functions EVAL and APPLY in M-expression syntax.] Abelson and Sussman's SICP, especially chapters 4 and 5 on the implementation of meta-circular and explicit-control evaluators. Steele and Gabriel's "The Evolution of LISP". ---------------------------------------------------------------- Subject: [1-6] What does CLOS, PCL, X3J13, CAR, CDR, ... mean? Glossary of acronyms: CAR Originally meant "Contents of Address portion of Register", which is what CAR actually did on the IBM 704. CDR Originally meant "Contents of Decrement portion of Register", which is what CDR actually did on the IBM 704. Pronounced "Cudder" /kUdd@r/ (as in "a cow chews its cdr"). The first syllable is pronounced like "could". LISP Originally from "LISt Processing" GUI Graphical User Interface CLOS Common Lisp Object System. The object oriented programming standard for Common Lisp. Based on Symbolics FLAVORS and Xerox LOOPS, among others. Pronounced either as "See-Loss" or "Closs". See also PCL. PCL Portable Common Loops. A portable CLOS implementation. Available by anonymous ftp from parcftp.xerox.com:pcl/. LOOPS Lisp Object Oriented Programming System. A predecessor to CLOS on Xerox Lisp machines. X3J13 Subcommittee of the ANSI committee X3 which is working on the ANSI Standardization of Common Lisp. ANSI American National Standards Institute dpANS draft proposed American National Standard (what an ANS is called while it's in the public review stage of standardization). CL Common Lisp SC22/WG16 The full name is ISO/IEC JTC 1/SC 22/WG 16. It stands for International Organization for Standardization/ International Electrotechnical Commission, Joint Technical Committee 1 Subcommittee 22 (full name "Information Technology -- Programming Languages and their Environments"), Working Group 16. This long-winded name is the ISO working group working on an international Lisp standard, (i.e., the ISO analogue to X3J13). CLtL1 First edition of Guy Steele's book, "Common Lisp the Language". CLtL2 Second edition of Guy Steele's book, "Common Lisp the Language". ---------------------------------------------------------------- Subject: [1-7] Lisp Job Postings The LISP-JOBS mailing list exists to help programmers find Lisp programming positions, and to help companies with Lisp programming positions find capable Lisp programmers. (Lisp here means Lisp-like languages, including Scheme.) Material appropriate for the list includes Lisp job announcements and should be sent to ai+lisp-jobs@cs.cmu.edu. Resumes should NOT be sent to the list. [Note: The 'ai+' part of the mailing list name is used for directing submissions to the appropriate mail-server. The list is NOT restricted to AI-related Lisp jobs -- all Lisp job announcements are welcome.] As a matter of policy, the contents of this mailing list is considered confidential and will not be disclosed to anybody. To subscribe, send a message to ai+query@cs.cmu.edu with subscribe lisp-jobs <First Name> <Last Name>, <Affiliation/Organization> in the message body. (If your mailer objects to the "+", send subscription requests to "ai+query"@cs.cmu.edu, job announcements to "ai+lisp-jobs"@cs.cmu.edu, etc.) For help on using the query server, send mail to ai+query@cs.cmu.edu with help in the message body. If you have any other questions, please send them to ai+@cs.cmu.edu ---------------------------------------------------------------- ;;; *EOF*